1. FIELD OF THE INVENTION
This invention relates to database processing.
2. RELATED ART
Database processing is a widely known and commercially significant aspect of the data processing field. A database is a collection of data organized into records. Computer operations which are performed on and/or using these data records are referred to as database processing. A database manager is the package of database processing operations used to access and manipulate the database.
Database processing commonly involves operations such as sorting and merging. Sorting, in the data processing sense, is the rearrangement of elements or keys in ascending or descending order. Merging, is the interleaving of elements or keys from two or more ordered lists. Conventionally, sorting and merging have been performed by software algorithms requiring significant amounts of processor execution time. In large databases, the processor execution time can be prohibitive, significantly degrading the performance of software database managers.
One well known method of sorting and merging is by way of a replacement selection algorithm. Replacement selection is the process of replacing one key by another in a tournament tree. An example of a replacement selection type multiway merge will be explained by reference to FIGS. 1 and 2.
FIG. 1 shows a 16 way tournament tree having 16 external nodes at its base (nodes 16-31) and 15 internal nodes in the tree body (nodes 1-15). An extra node (node 0) is appended at the top of the tree to indicate the champion of the tournament. Initially, the external nodes are filled with keys. The internal nodes of FIG. 1 are shown filled with "winners" assuming that the tree is regarded as a tournament to select the smallest key.
In replacement selection methods, as the winning key advances up the tree, it is replaced by the loser of the tournament at the previous level. FIG. 2 shows the same tree as FIG. 1 with the losers represented instead of the winners. Also, in the tree of FIG. 2, it will be observed that a next key "K" replaces the previous champion key "A" in external node 19. Assuming that the external nodes (16-31) are fed by ordered lists of keys, one only needs to compare the new comer "K" with the keys "C", "B", "D", "E" in order to determine the new state of the tree in order to determine a new tournament champion.
From FIGS. 1 and 2 it will be apparent that the illustrated replacement selection method requires four cycles of comparison to determine a tournament champion. For example, where the "K" at external node 19 is the next key to enter the tournament (as illustrated in FIG. 2), the four cycles of comparison proceed as follows:
1. "K" (node 19) is compared with "C" (node 9). Since "K" loses, it replaces "C" at node 9. The winner "C" is temporarily stored for the next cycle of comparison.
2. "C" (the winner of cycle 1) is compared with "B" (node 4). Since "C" loses, it replaces "B" at node 4; The winner "B" is temporarily stored for the next cycle of comparison.
3. "B" (the winner of cycle 2) is compared with "D" (node 2). Since "B" wins, it does not replace "D" but rather remains temporarily stored for the next cycle of comparison.
4. "B" (the winner of cycle 3) is compared with "E" (node 1). Since "B" wins it does not replace "E" but is instead moved to node 0. "B" is the tournament champion for this round.
As will be apparent from the foregoing example, the next new key would enter the tree from external node 17 (the source list of the previous champion, "B") and the next round of comparison would start from that point.
As is known in the art, offset codes and codeword comparisons can be used as an alternative to the comparison of actual keys within the structure of FIGS. 1 and 2. The use of offset value coding in a tournament tree is discussed in more detail in the article OFFSET VALUE CODING, by W. M. Conner, IBM technical Disclosure Bulletin Vol. 20, No. 7, December 1977, pp. 2832-2837, which is incorporated by reference, in its entirety, as if printed in full below.
One limitation of conventional tournament tree sorts and merges is that the number of cycles of comparison increases with the number of levels of the tree. Thus, in a replacement selection sort or merge using a tree having N levels of internal nodes, N cycles of comparisons are conventionally performed to determine a winner. These cycles of comparison, and the sort/merge operations in general can be a heavy burden on the central processors of even a large mainframe computer system. This is particularly so in light of the fact that operations on a large database can require the sorting or merging of lists comprising hundreds of millions of keys.
Multiway merging, sorting and replacement selection are discussed in more detail in the books SORTING AND SEARCHING, by Donald E. Knuth, published by the Addison-Wesley Publishing Company, Library of Congress Catalog Card. No. 67-26020, and SORTING AND SORT SYSTEMS, by Harold Lorin, published by Addison-Wesley Publishing Company, Inc., Library of Congress Catalog Card No. 73-2140, copyright 1975, both of which are incorporated by reference, in there entirety, as if printed in full below.